#include <stdio.h>
#include <stdlib.h>

// step 1# 创建链表节点  
typedef struct ListNode {
    int data;
    struct ListNode *next;
} ListNode;
// step 2# 创建链表结构体 ，其中真正存放链表的是 head
typedef struct LinkedList {
    int size;
    ListNode *head;
} List;
// step 3# 初始化链表 ：头指向 NULL ，size 为 0
void initList(List *list) {
    list->head = NULL;
    list->size = 0;
    return;
}
// step 4# 在链表中指定位置插入元素 ： 创建一个新节点，更新新节点的数据域
// 如果要插入的位置是头部 ，新节点挂链头部 ，头部设置为新节点
// 如果要插入的位置不是头部 ，新节点挂链要插入的位置的前一个节点的下一个节点 ，然后前一个节点摘链指向新节点
void insertAt(List *list, int index, int element) {
    if (index > list->size) {
        return;
    } 

    ListNode *newNode = (ListNode *)malloc(sizeof(ListNode));
    newNode->data = element;

    if (index == 0) {
        newNode->next = list->head;
        list->head = newNode;
        list->size++;
        return;
    }

    ListNode *cur = list->head;
    for(int i = 0; i < index - 1; i++) {
        cur = cur->next;
    }
    newNode->next = cur->next;
    cur->next = newNode; 
    list->size++;

    return;
}

void insertEnd(List *list, int element) {
    insertAt(list, list->size, element);    
}
// step 5# 删除指定位置的元素 ：先找到要删除的位置的前一个节点
// 用中间变量存放前一个节点的下一个节点的地址
// 把前一个节点指向下下个节点
// 然后释放中间变量指向的地址
int removeAt(List *list, int index) {
    if (index < 0 || index >= list->size) {
        return -1;
    }
    ListNode *deleteNode;
    ListNode *cur = list->head;
    for(int i = 0; i < index - 1; i++) {
        cur = cur->next;
    }
    deleteNode = cur->next;
    int deleteElement = deleteNode->data;
    cur->next = cur->next->next;
    deleteNode->next = NULL;
    free(deleteNode);
    return deleteElement;
}
// step 6# 销毁链表
// 用一个辅助指针来遍历链表 : 辅助指针先指向链表头部
// 只要辅助指针的下一个节点不为空，就一直循环遍历
// 利用一个中间变量来释放辅助指针当前指向的节点 : 
// 中间变量指向辅助指针指向的节点地址、辅助指针后移一位、释放中间变量
void destoryList(List *list) {
    ListNode *cur = list->head;
    while(cur->next != NULL) {
        ListNode *tmp = cur;
        cur = cur->next;
        free(tmp);
    }
    list->head = NULL;
    list->size = 0;
}

int main() {

    List *list;
    list = (List *)malloc(sizeof(List *));
    initList(list);
    insertAt(list, 0, 1);
    insertAt(list, 1, 2);
    insertEnd(list, 3);

    printf("%d\n", list->head->data);
    printf("%d\n", removeAt(list, 2));

    destoryList(list);
    printf("%d\n", list->size);


    return 0;
}